package model.ability;

import java.util.LinkedList;
import java.util.Queue;

import model.map.MapPoint;
import model.map.MapPointTreeNode;

/**
 * Placement algorithm which creates a cone shaped tree of
 * points in the direction that the caster is facing.
 * @author Zachary
 */
public class Cone extends PlacementAlgorithm {
	private final boolean[] branchType = {true,true,false,true,false};
	
	@Override
	public MapPointTreeNode calculateDisplacementSet(MapPoint direction, int range) {
		if(!MapPoint.isValidDirection(direction))
			return null;
		
		boolean[] branchType = instantiateBranchTypeArray(range);
		
		// set directions that the tree creation algorithm will use
		MapPoint outDirection = direction;
		MapPoint outLeftDirection = MapPoint.getNextCounterClockWiseDirection(direction);
		MapPoint outRightDirection = MapPoint.getNextClockWiseDirection(direction);
		
		MapPointTreeNode head = new MapPointTreeNode(ORIGIN);
		MapPointTreeNode firstChild = new MapPointTreeNode(MapPoint.addPoints(ORIGIN,direction));
		
		head.addChild(firstChild);
		
		// instantiate the level order queue and add the first element to it
		Queue<MapPointTreeNode> levelQueue = new LinkedList<MapPointTreeNode>();
		levelQueue.add(firstChild);
		
		int coneWidth = 1;
		
		// main tree creation loop
		for(int i = 1;i<range;++i){
			// if odd row, add to tree with branching pattern
			if(i % 2 == 1){
				// iterate across the row
				for(int j = 1;j<=coneWidth;j++){
					// branch at all points
					if(branchType[i / 2]){
						int midPoint = (1 + coneWidth) / 2;
						if(j < midPoint){
							addChildToTree(levelQueue,outRightDirection);
						}
						else if(j > midPoint){
							addChildToTree(levelQueue,outLeftDirection);
						}
						else{
							addChildToTreeNoRemove(levelQueue,outRightDirection);
							addChildToTreeNoRemove(levelQueue,outDirection);
							addChildToTree(levelQueue,outLeftDirection);
						}	
					}
					// branch only on the edges
					else{
						if(j == 1){
							addChildToTreeNoRemove(levelQueue,outRightDirection);
							addChildToTree(levelQueue,outDirection);
						}
						else if(j == coneWidth){
							addChildToTreeNoRemove(levelQueue,outDirection);
							addChildToTree(levelQueue,outLeftDirection);
						}
						else{
							addChildToTree(levelQueue,outDirection);
						}
					}
				}
				coneWidth += 2;
			}
			// if even row, just add the row straight down from the current row
			// to the tree
			else{
				for(int j = 1;j<=coneWidth;j++){
					addChildToTree(levelQueue,outDirection);
				}
			}
			
		}
		
		return head;
	}

	/**
	 * Helper method for calculateDisplacementSet() used to
	 * instantiate the branch type array.
	 * @param range
	 * @return
	 */
	private boolean[] instantiateBranchTypeArray(int range){
		// false = branch edge, true = branch all
		boolean[] branchType = range > 10 ? new boolean[(int)(range / 2 + .5)] : this.branchType;
		if(range > 10){
			int numBranchEdge = 2;
			for(int i = 5;i<(range / 2 + .5);i+=++numBranchEdge)
				branchType[i] = true;
		}
		return branchType;
	}
	
	/**
	 * Helper method for calculateDisplacementSet() used to
	 * add a branch to the tree.
	 * @param range
	 * @return
	 */
	private void addChildToTree(Queue<MapPointTreeNode> a, MapPoint direction){
		MapPointTreeNode n = a.remove();
		MapPoint location = n.getMapPoint();
		MapPoint newLocation = MapPoint.addPoints(location, direction);
		MapPointTreeNode child = new MapPointTreeNode(newLocation);
		n.addChild(child);
		a.add(child);
	}
	
	/**
	 * Helper method for calculateDisplacementSet() used to
	 * add a branch to the tree (does not remove node from
	 * queue).
	 * @param range
	 * @return
	 */
	private void addChildToTreeNoRemove(Queue<MapPointTreeNode> a, MapPoint direction){
		MapPointTreeNode n = a.peek();
		MapPoint location = n.getMapPoint();
		MapPoint newLocation = MapPoint.addPoints(location, direction);
		MapPointTreeNode child = new MapPointTreeNode(newLocation);
		n.addChild(child);
		a.add(child);
	}
	
}
